package com.masterlu.leetcode.daily.linkedlist.hard;

import com.masterlu.leetcode.daily.linkedlist.ListNode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * 合并k个升序l链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 * @Author：masterlu
 * @Date：2021/4/7 9:19 上午
 */
public class H23MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {

        //1.校验链表数组
        if (null == lists) {
            return null;
        }

        /**
         * 2.合并数组
         * 将链表依次存放到map中（序号为key，链表为value）
         * 将每个链表的头部元素存储在map中，元素为key，链表序号为value
         *
         */

        Map<Integer, ListNode> listNodeMap = new HashMap<>();
        Map<Integer, Integer> eleMap = new TreeMap<>();

        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                listNodeMap.put(i, lists[i]);
            }
        }

        ListNode head = null;
        ListNode curr = null;
        //利用treeSet对元素进行排序
        while (!listNodeMap.isEmpty()) {
            for (Map.Entry<Integer, ListNode> entry : listNodeMap.entrySet()) {
                if (entry.getValue() == null) {
                    continue;
                }
                eleMap.put(entry.getValue().val, entry.getKey());
            }
            if (eleMap.isEmpty()) {
                break;
            }
            Integer key = eleMap.keySet().iterator().next();

            if (head == null) {
                head = new ListNode(key);
                curr = head;
            } else {
                curr.next = new ListNode(key);
                curr = curr.next;
            }
            Integer value = eleMap.get(key);
            listNodeMap.put(value, listNodeMap.get(value).next);

        }

        return head;
    }

    /**
     * 抽象为2个有序队列合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {

        ListNode ans = null;
        for (ListNode list : lists) {
            ans = twoMergeList(ans, list);
        }

        return ans;
    }

    private ListNode twoMergeList(ListNode l1, ListNode l2) {
        //1.链表校验
        if (null == l1) {
            return l2;
        }
        if (null == l2) {
            return l1;
        }

        ListNode newHead = null, curr = null;
        int val = 0;

        while (null != l1 || null != l2) {
            int val1 = null == l1 ? Integer.MAX_VALUE : l1.val;
            int val2 = null == l2 ? Integer.MAX_VALUE : l2.val;

            if (val1 <= val2) {
                val = val1;
                l1 = l1.next;
            } else {
                val = val2;
                l2 = l2.next;
            }
            if (newHead == null) {
                newHead = new ListNode(val);
                curr = newHead;
            } else {
                curr.next = new ListNode(val);
                curr = curr.next;
            }
        }

        return newHead;
    }

    public static void main(String[] args) {
        //也可以使用优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(5);
        queue.offer(4);
        queue.offer(6);
        queue.offer(8);
        queue.offer(1);
        System.out.println(queue);
    }

}
